home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / tools / bison.lha / bison++-1.04 / warshall.c < prev   
C/C++ Source or Header  |  1989-06-09  |  2KB  |  119 lines
  1. /* Generate transitive closure of a matrix,
  2.    Copyright (C) 1984, 1989 Free Software Foundation, Inc.
  3.  
  4. This file is part of Bison, the GNU Compiler Compiler.
  5.  
  6. Bison is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 1, or (at your option)
  9. any later version.
  10.  
  11. Bison is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with Bison; see the file COPYING.  If not, write to
  18. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20.  
  21. #include <stdio.h>
  22. #include "machine.h"
  23.  
  24.  
  25. /* given n by n matrix of bits R, modify its contents
  26.    to be the transive closure of what was given.  */
  27.  
  28. void
  29. TC(R, n)
  30. unsigned *R;
  31. int n;
  32. {
  33.   register int rowsize;
  34.   register unsigned mask;
  35.   register unsigned *rowj;
  36.   register unsigned *rp;
  37.   register unsigned *rend;
  38.   register unsigned *ccol;
  39.  
  40.   unsigned *relend;
  41.   unsigned *cword;
  42.   unsigned *rowi;
  43.  
  44.   rowsize = WORDSIZE(n) * sizeof(unsigned);
  45.   relend = (unsigned *) ((char *) R + (n * rowsize));
  46.  
  47.   cword = R;
  48.   mask = 1;
  49.   rowi = R;
  50.   while (rowi < relend)
  51.     {
  52.       ccol = cword;
  53.       rowj = R;
  54.  
  55.       while (rowj < relend)
  56.     {
  57.       if (*ccol & mask)
  58.         {
  59.           rp = rowi;
  60.           rend = (unsigned *) ((char *) rowj + rowsize);
  61.  
  62.           while (rowj < rend)
  63.         *rowj++ |= *rp++;
  64.         }
  65.       else
  66.         {
  67.           rowj = (unsigned *) ((char *) rowj + rowsize);
  68.         }
  69.  
  70.       ccol = (unsigned *) ((char *) ccol + rowsize);
  71.     }
  72.  
  73.       mask <<= 1;
  74.       if (mask == 0)
  75.     {
  76.       mask = 1;
  77.       cword++;
  78.     }
  79.  
  80.       rowi = (unsigned *) ((char *) rowi + rowsize);
  81.     }
  82. }
  83.  
  84.  
  85. /* Reflexive Transitive Closure.  Same as TC
  86.    and then set all the bits on the diagonal of R.  */
  87.  
  88. void
  89. RTC(R, n)
  90. unsigned *R;
  91. int n;
  92. {
  93.   register int rowsize;
  94.   register unsigned mask;
  95.   register unsigned *rp;
  96.   register unsigned *relend;
  97.  
  98.   TC(R, n);
  99.  
  100.   rowsize = WORDSIZE(n) * sizeof(unsigned);
  101.   relend = (unsigned *) ((char *) R + n*rowsize);
  102.  
  103.   mask = 1;
  104.   rp = R;
  105.   while (rp < relend)
  106.     {
  107.       *rp |= mask;
  108.  
  109.       mask <<= 1;
  110.       if (mask == 0)
  111.     {
  112.       mask = 1;
  113.       rp++;
  114.     }
  115.  
  116.       rp = (unsigned *) ((char *) rp + rowsize);
  117.     }
  118. }
  119.